Formalni jezik

Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). Ako se pravilno ne potkrijepe pouzdanim izvorima, sporne rečenice i navodi mogli bi biti izbrisani. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci te nakon toga možete ukloniti ovaj šablon.

U matematici, logici i računarstvu, formalni jezik ${\displaystyle {\boldsymbol {L}}}$ se sastoji od skupa konačnih nizova elemenata konačnog skupa ${\displaystyle {\boldsymbol {A}}}$ znakova (simbola). Matematički, to je neuređen par ${\displaystyle {\boldsymbol {L}}=\{{\boldsymbol {A}},{\boldsymbol {F}}\}.}$ Među najuobičajenijim primjenama, formalni jezik može biti shvaćen kao:

• kolekcija riječi

ili

• kolekcija rečenica

U prvom slučaju, skup ${\displaystyle {\boldsymbol {A}}}$ se zove abeceda jezika ${\displaystyle {\boldsymbol {L}}}$, a elementi skupa ${\displaystyle {\boldsymbol {F}}}$ se zovu riječi. U drugom slučaju, skup ${\displaystyle {\boldsymbol {A}}}$ se zove leksikon ili vokabular skupa ${\displaystyle {\boldsymbol {F}}}$, dok se elementi skupa ${\displaystyle {\boldsymbol {F}}}$ zovu rečenice. Matematička teorija koja se općenito bavi proučavanjem formalnih jezika se zove teorija formalnih jezika.

Kao primjer formalnog jezika, abeceda može biti ${\displaystyle \left\{a,b\right\}}$, a riječ (string, niz znakova) nad tim alfabetom može biti ${\displaystyle ababba\,}$.

Tipični jezik nad abecedom, koji sadrži tu riječ, bi bio skup svih riječi koje sadrže isti broj znakova ${\displaystyle a\,}$ and ${\displaystyle b\,}$.

Prazan niz (ili prazna riječ) je riječ dužine 0, i često se označava znakom ${\displaystyle e\,}$, ${\displaystyle \epsilon \,}$ ili ${\displaystyle \Lambda \,}$. Iako je abeceda konačan skup i svaka riječ je konačne dužine, jezik može imati beskonačno mnogo riječi (jer dužina riječi koje sadrži ne mora nužno imati gornju granicu).

Često postavljano pitanje o formalnim jezicima jest "koliko je teško odlučiti da li zadana riječ pripada nekom određenom jeziku?" Ovo je područje proučavanja teorije računanja i teorije složenosti.